#pragma once
#include "common.h"
void AdjustDown(vector<int>& nums, int parent, int n) {
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && nums[child + 1] > nums[child]) {
            ++child;
        }
        if (nums[parent] < nums[child]) {
            swap(nums[parent], nums[child]);
        }
        parent = child;
        child = 2 * parent + 1;
    }
}


void MakeHeap(vector<int>& nums) {
    int n = nums.size();
    int parent = (n - 2) / 2;
    for (int i = parent; i >= 0; --i) {
        AdjustDown(nums, i, n);
    }
}


void HeapSort(vector<int>& nums) {
    MakeHeap(nums);
    int n = nums.size();
    for (int i = n - 1; i >= 0; --i) {
        swap(nums[i], nums[0]);
        AdjustDown(nums, 0, --n);
    }
}